/*
@Time : 2019/8/20 0020 20:06
@Author : visons
*/
package main

import (
	"fmt"
	"math/rand"
	"time"
)

//冒泡排序 时间复杂度O(n^2)
func BubbleSort(data []int) []int {
	for i := 0; i < len(data); i++ {
		for j := 1; j < len(data)-i; j++ {
			if data[j] < data[j-1] {
				data[j-1], data[j] = data[j], data[j-1]
			}
		}
	}
	return data
}

//选择排序
func SelectSort(data []int) {
	for i := 0; i < len(data)-1; i++ {
		min := i
		for j := i; j < len(data)-1; j++ {
			if data[min] > data[j] {
				min = j
			}
		}
		data[i], data[min] = data[min], data[i]
	}
}

//插入排序 时间复杂度O(n^2)
func InsertSort(data []int) {
	if data == nil || len(data) < 2 {
		return
	}
	for i := 1; i < len(data); i++ {
		for j := i; j > 0; j-- {
			if data[j] < data[j-1] {
				data[j], data[j-1] = data[j-1], data[j]
			}
		}

	}
}

//快速排序
func QuickSort(lst []int, start, end int) {
	if start >= end {
		return
	}
	low := start
	high := end
	mid := lst[start]

	for low < high {
		for low < high && lst[high] >= mid {
			high--
		}
		//出了循环说明 high 小于等于 mid 则需要交换位置
		lst[high], lst[low] = lst[low], lst[high]

		for low < high && lst[low] < mid {
			low++
		}
		// 出了循环说明 low 大于等于mid 则需要交换位置
		lst[low], lst[high] = lst[high], lst[low]
	}
	// 大的循环退出以后就找到了 mid的位置,此时mid 左边的都小于mid, 右边都大于mid,以 mid 为界限再排序左右两边
	lst[low] = mid
	QuickSort(lst, start, low-1) // 排序左边的
	QuickSort(lst, low+1, end)   // 排序右边的
}

func QuickSort2(data []int, low, hig int) {
	if low >= hig {
		return
	}
	left := low
	right := hig

	mid := data[low]
	for left < right {
		for left < right && data[right] >= mid {
			right--
		}
		data[right], data[left] = data[left], data[right]

		for left < right && data[left] < mid {
			left++
		}
		data[right], data[left] = data[left], data[right]
	}
	data[left] = mid
	QuickSort2(data, low, left-1)
	QuickSort2(data, left+1, hig)
}

//二分查找
func BinarySearch(num []int, v int) int {
	hig := len(num)
	if hig == 0 {
		return -1
	}

	low := 0
	for low <= hig {
		mid := (hig + low) / 2
		if num[mid] == v {
			return mid
		}
		if num[mid] < v {
			low = mid + 1
		} else {
			hig = mid - 1
		}
	}
	return -1
}

//堆调整
func adjust_heap(arr []int, i, size int) {
	if i <= (size-2)/2 {
		//左右子节点
		l, r := 2*i+1, 2*i+2
		m := i
		if l < size && arr[l] > arr[m] {
			m = l
		}
		if r < size && arr[r] > arr[m] {
			m = r
		}
		if m != i {
			arr[m], arr[i] = arr[i], arr[m]
			adjust_heap(arr, m, size)
		}
	}
}

//建堆
func build_heap(arr []int) {
	size := len(arr)
	//从最后一个子节点开始向前调整
	for i := (size - 2) / 2; i >= 0; i-- {
		adjust_heap(arr, i, size)
	}
}

func HeapSort(arr []int) {
	size := len(arr)
	build_heap(arr)
	for i := size - 1; i > 0; i-- {
		//顶部arr[0]为当前最大值,调整到数组末尾
		arr[0], arr[i] = arr[i], arr[0]
		adjust_heap(arr, 0, i)
	}
}

//合并
func Merge(arr []int, l, mid, r int) {
	// 分别复制左右子数组
	n1, n2 := mid-l+1, r-mid
	left, right := make([]int, n1), make([]int, n2)
	copy(left, arr[l:mid+1])
	copy(right, arr[mid+1:r+1])
	i, j := 0, 0
	k := l
	for ; i < n1 && j < n2; k++ {
		if left[i] <= right[j] {
			arr[k] = left[i]
			i++
		} else {
			arr[k] = right[j]
			j++
		}
	}
	for ; i < n1; i++ {
		arr[k] = left[i]
		k++
	}
	for ; j < n2; j++ {
		arr[k] = right[j]
		k++
	}
}

//分治
func MergeSort(arr []int, l, r int) {
	if l < r {
		mid := (l + r - 1) / 2
		MergeSort(arr, l, mid)
		MergeSort(arr, mid+1, r)
		Merge(arr, l, mid, r)
	}
}

func test() {
	rand.Seed(time.Now().UnixNano())
	data := []int{20, 50, 40, 10, 60, 30, 5, 8, 36, 5, 89, 3, 12, 3, 465, 68, 20, 1, 354, 56, 2, 546, 78, 80, 2, 3, 567, 678, 8, 9, 234, 546, 678, 3, 45, 5, 77, 24, 34, 5, 46, 3, 534, 654, 6, 345, 344, 6534,
		345, 34, 53445, 34, 46, 344, 53, 43, 4634, 6, 457, 67, 85, 45, 3, 54, 7566, 8, 5, 3, 4, 756, 78, 4, 63, 5, 34, 7547, 65, 867, 9, 8, 13, 23, 5434, 6, 23,
		456, 67, 567, 7, 456546, 243, 456, 67, 213, 345, 57, 345, 547, 345, 5656, 57, 324, 132, 22, 345, 546, 345456457, 342345, 4567, 78, 789, 345, 234, 546, 3245345, 5467, 345, 3453, 6, 335434, 65, 7343,
		345, 456, 67, 354, 456, 567, 35, 547, 3456, 5467, 756, 7567, 568, 43, 46457, 586, 4565, 856, 34, 53456, 7, 568, 345, 345, 457, 568, 345, 457, 5668, 3, 5, 35, 35434, 665, 863, 453456, 457, 567,
		45645, 658, 224, 25, 436, 7, 567, 567, 4, 64, 57, 5678, 568, 679, 780, 234, 24, 235, 456, 547, 679, 780, 242, 423, 534, 64575, 34, 5, 47, 68, 35, 36, 578, 6, 8678}

	start := time.Now()
	//BubbleSort(data)
	//SelectSort(data)
	//InsertSort(data)

	//QuickSort2(data,0,len(data)-1)
	//fmt.Println(data)
	//HeapSort(data)
	//MergeSort(data,0,len(data)-1)

	fmt.Println(time.Now().Sub(start))
	fmt.Println(data)
}
